package com.mdnote.structure.sort;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/26
 * @description 插入排序
 */
public class InsertSort {

    /**
     * 排序
     * @param source 数组
     */
    public static void sort(int[] source) {
        // 指定有序列表的最后一个数字
        int insertIndex = 0;
        // 无序列表的第一个数的值
        int currentValue = 0;

        // 遍历无序列表
        for (int i = 1; i < source.length; i++) {
            // 获取当前的值
            currentValue = source[i];
            // 指定有序列表的最后一个元素
            insertIndex = i - 1;
            // 遍历有序列表，看看有没有位置可以放，有的话直接把对应的位置后面的元素全部向后移
            while (insertIndex >= 0 && currentValue < source[insertIndex]) {
                source[insertIndex + 1] = source[insertIndex];
                insertIndex--;
            }
            // 把元素放到对应的位置
            source[insertIndex + 1] = currentValue;
        }
    }

    /**
     * 优化一下
     * @param source
     */
    public static void sortPlus(int[] source) {
        // 指定有序列表的最后一个数字
        int insertIndex = 0;
        // 无序列表的第一个数的值
        int currentValue = 0;

        // 遍历无序列表
        for (int i = 1; i < source.length; i++) {
            // 获取当前的值
            currentValue = source[i];
            // 指定有序列表的最后一个元素
            insertIndex = i - 1;
            // 遍历有序列表，看看有没有位置可以放，有的话直接把对应的位置后面的元素全部向后移
            while (insertIndex >= 0 && currentValue < source[insertIndex]) {
                source[insertIndex + 1] = source[insertIndex];
                insertIndex--;
            }
            // 把元素放到对应的位置
            if (insertIndex + 1 != i) {
                source[insertIndex + 1] = currentValue;
            }
        }
    }
    public static void main(String[] args) {
        int[] data = {11, 22, 55, 10, 23};
        sort(data);
        System.out.println(Arrays.toString(data));
    }
}
